// re2rust $INPUT -o $OUTPUT

const NONE: usize = std::usize::MAX;
const MTAG_ROOT: usize = NONE - 1;

// An m-tag tree is a way to store histories with an O(1) copy operation.
// Histories naturally form a tree, as they have common start and fork at some
// point. The tree is stored as an array of pairs (tag value, link to parent).
// An m-tag is represented with a single link in the tree (array index).
type MtagTrie = Vec::<MtagElem>;
struct MtagElem {
    elem: usize, // tag value
    pred: usize, // index of the predecessor node or root
}

// Append a single value to an m-tag history.
fn add_mtag(trie: &mut MtagTrie, mtag: usize, value: usize) -> usize {
    trie.push(MtagElem{elem: value, pred: mtag});
    return trie.len() - 1;
}

// Recursively unwind tag histories and collect version components.
fn unwind(trie: &MtagTrie, x: usize, y: usize, str: &[u8], ver: &mut Ver) {
    // Reached the root of the m-tag tree, stop recursion.
    if x == MTAG_ROOT && y == MTAG_ROOT { return; }

    // Unwind history further.
    unwind(trie, trie[x].pred, trie[y].pred, str, ver);

    // Get tag values. Tag histories must have equal length.
    assert!(x != MTAG_ROOT && y != MTAG_ROOT);
    let (ex, ey) = (trie[x].elem, trie[y].elem);

    if ex != NONE && ey != NONE {
        // Both tags are valid string indices, extract component.
        ver.push(s2n(&str[ex..ey]));
    } else {
        // Both tags are NONE (this corresponds to zero repetitions).
        assert!(ex == NONE && ey == NONE);
    }
}

type Ver = Vec::<u32>; // unbounded number of version components

fn s2n(str: &[u8]) -> u32 { // convert a pre-parsed string to a number
    let mut n = 0;
    for i in str { n = n * 10 + *i as u32 - 48; }
    return n;
}

fn parse(yyinput: &[u8]) -> Option<Ver> {
    assert_eq!(yyinput.last(), Some(&0)); // expect null-terminated input

    let (mut yycursor, mut yymarker) = (0, 0);
    let mut mt: MtagTrie = Vec::new();

    // User-defined tag variables that are available in semantic action.
    let (t1, t2, t3, t4);

    // Autogenerated tag variables used by the lexer to track tag values.
    /*!stags:re2c format = 'let mut @@ = NONE;'; */
    /*!mtags:re2c format = 'let mut @@ = MTAG_ROOT;'; */

    /*!re2c
        re2c:api = default;
        re2c:define:YYCTYPE = u8;
        re2c:define:YYMTAGP = "@@ = add_mtag(&mut mt, @@, yycursor);";
        re2c:define:YYMTAGN = "@@ = add_mtag(&mut mt, @@, NONE);";
        re2c:yyfill:enable = 0;
        re2c:tags = 1;

        num = [0-9]+;

        @t1 num @t2 ("." #t3 num #t4)* [\x00] {
            let mut ver: Ver = Vec::new();
            ver.push(s2n(&yyinput[t1..t2]));
            unwind(&mt, t3, t4, yyinput, &mut ver);
            return Some(ver);
        }
        * { return None; }
    */
}

fn main() {
    assert_eq!(parse(b"1\0"), Some(vec![1]));
    assert_eq!(parse(b"1.2.3.4.5.6.7\0"), Some(vec![1, 2, 3, 4, 5, 6, 7]));
    assert_eq!(parse(b"1.2.\0"), None);
}
